package util;

import graph.Graph;
import graph.Tree;
import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author Admin
 */
public abstract class AbstractColouring<V, E extends Graph.Edge<V>> {

    protected Map<V, Boolean> marked = new HashMap<V, Boolean>();
    protected Tree<V, E> tree;

    public AbstractColouring(Tree<V, E> tree) {
        this.tree = tree;
    }

    public Map<V, Boolean> marked() {
        return marked;
    }

    protected ColourDegree getColourDegree(V v) {
        ColourDegree degree = new ColourDegree();
        if (marked.containsKey(v) && marked.get(v)) {
            degree.bColour = tree.degree(v);
            return degree;
        }
        for (V w : tree.neighbors(v)) {
            degree.increase(marked.containsKey(w) && marked.get(w));
        }
        return degree;
    }

    protected boolean is2aliec(V r) {
        ColourDegree dr = getColourDegree(r);
        for (V v : tree.children(r)) {
            ColourDegree dv = getColourDegree(v);
            if (dv.aColour == dr.aColour && dv.bColour == dr.bColour) {
                return false;
            }
            is2aliec(v);
        }
        return true;
    }

    public abstract void colour();
}
